//
// Created by yanhai on 2021/1/10.
//

/**
 * 判断链表是否有环？
 * 并确定环的入口。
 */

#include <stdio.h>
#include "link_common.h"

/**
 * 检测链表是否有环
 * 原理：使用快慢指针，p1 p2同时从头节点出发。
 *      p1每次移动1步，p2每次移动2步，
 *      如果在某一个时刻，p1==p2，则有环
 *      如果p2==NULL，则没环
 * @param T
 * @return
 */
bool link_ring_check(link *T)
{
    link_node *p1, *p2;
    p1 = p2 = T->root;

    // 由于p2走的快，所以只判断p2即可。
    while (p2->next && p2->next->next) {
        p1 = p1->next;
        p2 = p2->next->next;
        if (p1 == p2) {
            return true;
        }
    }

    return false;
}

/**
 * 找到环的入口节点
 * 原理：接上面的函数的原理。
 *      当p1==p2时，使用1个新的指针（这里是复用p2），指向链表开头
 *      p1 p2同步向后移动，每次移动1步，
 *      当p1==p2时，就是环的入口（不懂如何证明。。。。）
 * @param T
 * @return NULL：没有环
 */
link_node *link_ring_detect(link *T)
{
    link_node *p1, *p2;
    p1 = p2 = T->root;

    while (p2->next && p2->next->next) {
        p1 = p1->next;
        p2 = p2->next->next;

        if (p1 == p2) {     // 有环
            p2 = T->root;

            while (p1 != p2) {
                p1 = p1->next;
                p2 = p2->next;
            }
            return p1;
        }
    }
    return NULL;
}

/**
 * 测试是否有环
 * @param T
 */
void link_ring_check_test(link *T)
{
    if (link_ring_check(T)) {
        printf("%s：有环\n", __FUNCTION__);
    } else {
        printf("%s：没有环\n", __FUNCTION__);
    }
}

/**
 * 确定环入口测试
 * @param T
 */
void link_ring_detect_test(link *T)
{
    link_node *node = link_ring_detect(T);
    if (node == NULL) {
        printf("%s: 没有环\n", __FUNCTION__);
    } else {
        printf("%s: 环的入口的元素值为：%d\n", __FUNCTION__, node->key);
    }
}

int main()
{
    link T = link_create_from_index(20, false);
    link_print(&T);

    ///////////////// 没有环时 /////////////////
    printf("\n=== 没有环时\n");
    link_ring_check_test(&T);
    link_ring_detect_test(&T);

    ////////////////// 使有环 /////////////////
    // 让链表有环
    link_node *node = link_find(&T, 7); // 环入口元素的值为7
    assert(node != NULL);
    link_append(&T, node);

    ////////////////// 有环时 /////////////////
    printf("\n=== 有环时\n");
    link_ring_check_test(&T);
    link_ring_detect_test(&T);

    // todo 释放有环链表
    //  先解开环，再按照正常链表释放
    //  从链表开始向后遍历，记录第2次遇到入口点的前面的节点，让该节点的next为NULL
//    link_destroy(&T);
    return 0;
}
